package tree;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author kaho
 * @since 2021/3/3
 */
public class _257_二叉树的所有路径 {

    /**
     * 给定一个二叉树，返回所有从根节点到叶子节点的路径。
     *
     * 说明: 叶子节点是指没有子节点的节点。
     * @param root
     * @return
     */
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        List<Integer> cur = new ArrayList<>();
        dfs(root, cur, result);
        return result;
    }

    private void dfs(TreeNode root, List<Integer> cur, List<String> result) {
        if (root == null) {
            return;
        }
        cur.add(root.val);
        if (root.left == null && root.right==null) {
            result.add(cur.stream().map(Object::toString)
                    .collect(Collectors.joining("->")));
            return;
        }

        dfs(root.left, cur, result);
        if (!cur.isEmpty() && root.left!=null) {
           cur.remove(cur.size()-1);
        }
        dfs(root.right, cur, result);
        if (!cur.isEmpty() && root.right != null) {
            cur.remove(cur.size()-1);
        }
    }
}
